package PenTest.Soluation11;

import java.util.*;
import java.io.*;


public class Solution {


    /**
     * 题目： 寻找最长无重复连续子数组
     * 哈希表 + 滑动窗口
     *
     * 哈希表统计
     * 滑动窗口 更新结果
     *
     * @param arr
     * @return
     */
    public int maxLength (int[] arr) {

        // 长度
        int len = arr.length;
        // 创建一个哈希表来统计数据
        Map<Integer, Integer> hash = new HashMap<>();

        // 存储结果
        int ret = -1;

        // 进行滑动窗口
        for (int left = 0, right = 0; right < len ; right++) {

            // 入窗口
            int num = arr[right];
            hash.put(num, hash.getOrDefault(num, 0) + 1);


            while (hash.get(arr[right]) >= 2) {
                // 更新结果
                ret = Math.max(ret, right - left);

                // 出窗口
                hash.put(arr[left], hash.get(arr[left]) - 1);
                left++;
            }

            // 更新结果
            ret = Math.max(ret, right - left+1);
        }

        return ret;
    }
}


/**
 * 题目： 重排相邻不重复的数组
 *
 * 1. 先统计次数最多的个数的字符
 * 2. 然后判断 maxcount > (n+1)/2 不能重排
 * 3. 先放次数最多的字符到 偶数下标位
 *
 * 4. 最终放到剩余的偶数下标位，
 * 5. 当偶数下标位满了， 就调整到奇数下标位。
 *
 */




 class Main{
    public static void main(String[] args) {

//         输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] str = in.next().toCharArray();

        // 找出出现最多的字符的次数
        char maxchar = '0';
        int maxcount= 0;

        // 用哈希表来统计每个字符出现的个数
        int[] hash = new int[26];

        for(int i =0; i<n; i++) {
            // 字符
            char ch = str[i];

            // 更新最大次数
            if(++hash[ch-'a'] > maxcount) {
                maxcount = hash[ch-'a'];
                maxchar= ch;
            }
        }


        // 判断是否能重组
        if(maxcount > (n+1)/2) {
            System.out.println("no");
            return;
        }


//         存放结果
        char[] ret = new char[n];


        // 先放入最大次数的字符
        int i =0;
        while(maxcount-- != 0) {
            ret[i] = maxchar;
            i += 2;
        }

        for(int j = 0; j < 26; j++) {
            int count = hash[j];

            // 存放剩下的字符
            while(count-- != 0 && (char)('a' + j) != maxchar) {
                if(i >= n) {
                    i=1;
                }

                // 存放该字符
                ret[i] = (char)('a' + j);
                i += 2;

            }
        }


//         输出
        System.out.println("yes");
        for(int j=0; j < n; j++) {
            System.out.print(ret[j]);
        }

    }
}


/**
 * 题目： dd分组
 * 1. 分类暴力枚举 1~ 最大个数, 一旦满足 <= m 就break 输出
 *
 *
 */


 class Main2{
    public static void main(String[] args) {

//         输入
        Scanner in = new Scanner(System.in);
        int  n = in.nextInt();
        long  m  = in.nextInt();

//         哈希统计
        long[] hash = new long[n+1];


//         记录该个数
        long maxCount = 0;
        for(int i = 0 ;i < n; i++) {
            int num = in.nextInt();

            // 记录最大次数的值
            if(++hash[num] >= maxCount) {
                maxCount= hash[num];
            }

        }


        // 进行暴力枚举
        long ret = -1;
        for(int i = 1; i <= maxCount ;i++) {
            long result = 0;

            // 开始遍历
            for(int j = 1; j <= n; j++) {
                result += (hash[j] / i);
                result += (hash[j] % i == 0 ? 0 : 1);
            }

            // 一旦符合 组数就返回结果
            if(result <= m) {
                ret = i;
                break;
            }
        }

//         输出
        System.out.println(ret);

    }
}


/**
 * 题目： dd 分组
 *
 * 进行二分算法
 *
 * 在原来的基础上，寻找左边界的最小值
 *
 */

 class Main3{
    public static void main(String[] args) {

//         输入
        Scanner in = new Scanner(System.in);
        int  n = in.nextInt();
        int  m  = in.nextInt();

//         哈希统计
        int[] hash = new int[n+1];


//         记录该个数
        int maxCount = 0;
        for(int i = 0 ;i < n; i++) {
            int num = in.nextInt();

            // 记录最大次数的值
            if(++hash[num] >= maxCount) {
                maxCount= hash[num];
            }

        }


        // 进行二分算法
        int left =1 , right = maxCount;
        int result =0;
        boolean flg =false;
        while(left != right) {


            // 寻找左边界的最小值
            int mid = left + ((right-left)/2);
            result = 0;

            // 开始遍历
            for(int j = 1; j <= n; j++) {
                result += (hash[j] / mid);
                result += (hash[j] % mid == 0 ? 0 : 1);
            }

            // 一旦符合 组数就返回结果
            if(result <= m) {
                right = mid;
                flg =true;
            } else {
                left = mid +1;
            }
        }


//         输出
        System.out.println(flg ? right : -1);

    }
}


/**
 * 题目：删除相邻数字的最大分数
 *
 * 进行状态转移
 * 1. dp 表示 填入的数字
 * 2. fp 表示不填入的该数字
 *
 * 最终返回 dp[max] 和 fp[max] 中的最大值
 */


 class Main4 {
    public static void main(String[] args) {

        // 输入
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        // 记录个数
        int[] hash = new int[10001];
        int sz = 0;
        int max = 0;

        // 输入并记录
        for(int i=0; i<n; i++) {
            int x= in.nextInt();
            hash[x]++;
            max = Math.max(max,x);
        }



        // 状态转移方程
        int[] dp = new int[max+1];
        int[] fp  = new int[max+1];

        // 初始化
        dp[0] = 0;
        fp[0] = 0;

        // 进行状态转移
        for(int i=1; i <= max;i++) {
            // 进行状态转移
            dp[i] = (hash[i] * i) + fp[i-1];
            fp[i] = Math.max(fp[i-1],dp[i-1]);
        }

        // 最终返回两者的最大
        System.out.println(Math.max(dp[max], fp[max]));
    }
}





 class Main5 {
    public static void main(String[] args) {

        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

        long[] happy = new long[n];
        long[] shy = new long[n];

        for (int i = 0; i < n; i++) {
            happy[i] = in.nextLong();
        }

        for (int i = 0; i < n; i++) {
            shy[i] = in.nextLong();
        }


        long hy = 0;
        long hymax =0;

        long sy = 0;
        long symin = 0;

        int start = 0;
        // 滑动窗口
        // 满的情况


        int left = 0, right = 0;
        for (; right < n; right++ ) {

            // 统计总和
            hy += happy[right];
            sy += shy[right];

            if ( right - left + 1 == k) {

                // 总和一旦超过就记录
                // 更新结果
                if (hy > hymax) {
                    // 快乐值优先更新
                    hymax = hy;
                    start = left;
                } else if(hy == hymax) {

                    // 相等的情况下，羞耻度越低就更新
                    if(sy < symin) {
                        symin = sy;
                        start = left;
                    }
                }

                // 出窗口
                hy -= happy[left];
                sy -= shy[left];
                left++;
            }


        }




        System.out.println(start + 1);

        System.out.println(symin);

    }
}


/**
 *
 * 题目：小乐乐改数字
 * 偶数全部变为 0
 * 奇数全部变为 1
 * 处理方式： 转化为字符串处理
 */



 class Main6 {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        // 转化成字符串
        char[] str = String.valueOf(num).toCharArray();

        // 存储返回值
        StringBuilder ret = new StringBuilder();
        // 存储结果
        for (int i = 0; i < str.length; i++) {
            int x = (str[i] - '0');
            if (x % 2 == 0 ) {
                if (ret.length() != 0) {
                    ret.append("0");
                }
            } else {
                ret.append("1");
            }
        }

        // 判断为 空的情况
        if (ret.length() == 0) {
            System.out.println(0);
        } else {
            System.out.println(Long.valueOf(ret.toString()));
        }
    }
}



class Test {
    public static void main(String[] args) {
        Map<Long,Long> hash = new HashMap<>();
        hash.put(2L,4L);
        hash.put(7L,9L);
        hash.put(1L,5L);


    }
}


/**
 * 题目： 01背包
 *
 * 1. dp映射下标
 * 2. 在 j 位置中寻找到 最重的
 * 3. 当前位置不放入背包的 dp[j] , j 体积最重
 * 4. 在当前位置 放入背包的 dp[j- 当前位置的体积] + 该重物 ,
 * 5. 寻找两者的最大值
 */

 class Solution1 {

    public int knapsack (int V, int n, int[][] vw) {
        int[] dp = new int[1010];

        // 开始遍历
        for(int i=0; i<n;i++) {
            // 进行逆置状态转移
            for(int j=V;j >= vw[i][0];j--) {
                dp[j] = Math.max(dp[j],dp[j-vw[i][0]]+vw[i][1] );
            }
        }

        return dp[V];
    }
}


/**
 * 题目： chika和蜜柑
 * 1.  用类的方式来整合
 * 2. 排序策略： 甜多的优先， 相同甜就酸少优先
 */


class Orange {
    // 甜度
    int sweet;
    // 酸度
    int sour;

    public Orange() {

    }

    public Orange(int sweet) {
        this.sweet = sweet;

    }


}


 class Main7 {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

        Orange[] fruit = new Orange[n];

//         初始化酸度
        for(int i=0; i<n; i++) {
            fruit[i] =new Orange();
            fruit[i].sour = in.nextInt();

        }



//         初始化甜度
        for(int i=0; i<n; i++) {
            fruit[i].sweet = in.nextInt();
        }


        // 进行排序
        Arrays.sort(fruit,(x,y)->{
            if(x.sweet == y.sweet) {
                return x.sour - y.sour;
            }

            return y.sweet- x.sweet;
        });


        long sweetSum =0, sourSum=0;

        // 最终把满意的结果累加
        for(int i = 0; i < k;i++) {
            sweetSum += fruit[i].sweet;
            sourSum += fruit[i].sour;
        }

        // 输出
        System.out.println(sourSum + " " + sweetSum);
    }
}






 class Solution6 {


     /**
      * 题目： 压缩字符串
      *
      * 1. 计数器法
      * @param param
      * @return
      */


    public String compressString (String param) {
        // 存储结果
        StringBuilder ret = new StringBuilder();

        // 特殊情况
        if ( param.length() == 0) return ret.toString();

        char[] str = param.toCharArray();


        int count = 1;
        char ch = str[0];
        for (int i = 1; i < str.length; i++) {

            // 相同计算器就 + 1
            if (ch == str[i]) {
                count++;
            } else {
                // 不相同就入字符
                ret.append(ch);
                if (count > 1) {
                    // 不为 1 入个数
                    ret.append(count);
                }

                // 重新更新结果
                ch = str[i];
                count = 1;
            }
        }

        // 最后一个字符
        ret.append(str[str.length-1]);
        if (count > 1) {
            // 不为 1 入个数
            ret.append(count);
        }


        return ret.toString();
    }
}







 class Solutio2 {

     /**
      * 题目： 压缩字符串
      *
      * 1. 双指针算法
      *
      * @param param
      * @return
      */

    public String compressString (String param) {
        // 存储结果
        StringBuilder ret = new StringBuilder();

        char[] str = param.toCharArray();

        // 双指针
        int left = 0,right =0;
        while(left < str.length) {

            // 只有前后相等时，right 才向后走
            while(right + 1 < str.length && str[right] == str[right+1]) {
                right++;
            }

            // 加入字符
            ret.append(str[left]);

            // 不为 1加入数字
            if(right - left + 1 > 1) {
                ret.append(right - left +1);
            }

            // 让 left 走道 right 后一位
            left = right + 1;

            // right再到 left 的位置重新寻找相同的字符
            right = left ;
        }

        // 最终转化返回
        return ret.toString();
    }
}


/**
 * 题目： 比那名居的桃子
 * 1. 滑动窗口算法
 */


 class Main8 {


    public static void main(String[] args) {
//         输入
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();

        long[] happy = new long[n];
        long [] shy = new long[n];
//         输入快乐值
        for(int i=0; i<n; i++) {
            happy[i] = in.nextLong();
        }

//      输入害羞值
        for(int i=0; i<n; i++) {
            shy[i] = in.nextLong();
        }

//         进行滑动窗口
        long happySum =0;
        long happyMax = Long.MIN_VALUE;
        long shySum = 0;
        long shyMin = Long.MAX_VALUE;

        // 记录结果
        int  ret = 0;

        for(int left = 0, right =0;right < n ; right ++) {

//             入窗口
            happySum += happy[right];
            shySum += shy[right];

            if(right - left + 1 == k) {
                // 快乐值更大时
                if(happySum > happyMax) {
//                     更新最大
                    happyMax = happySum ;
                    shyMin = shySum;
//                     天数记录
                    ret = left + 1;
                } else if(happySum == happyMax) {
                    // 快乐值相等值
                    // 害羞更小就更新
                    if(shySum < shyMin) {
                        ret = left + 1;
                        shyMin = shySum ;
                        happyMax = happySum;

                    }
                }


//                 出窗口
                happySum -= happy[left];
                shySum -= shy[left++];
            }
        }

//         输出
        System.out.println(ret);


    }


}


/**
 * 题目： 比那名居的桃子
 * 1. 前缀和算法
 */


 class Main9 {


    public static void main(String[] args) {
//         输入
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();

        long[] happy = new long[n];
        long [] shy = new long[n];
//         输入快乐值
        for(int i=0; i<n; i++) {
            happy[i] = in.nextLong();
        }

//      输入害羞值
        for(int i=0; i<n; i++) {
            shy[i] = in.nextLong();
        }


        // 进行前缀和算法
        long[] happyDp = new long[n+1];
        long[] shyDp = new long[n+1];

        for(int i=1; i<=n; i++) {
            // 进行状态转移
            happyDp[i] = happyDp[i-1] + happy[i-1];
            shyDp[i] =  shyDp[i-1] + shy[i-1];
        }

        long happyMax = Long.MIN_VALUE;
        long shyMin = Long.MAX_VALUE ;
        int ret = 0;

        // 获取最大
        for(int i =0; i + k <= n ; i++) {
            // 得到该段长度
            if(happyDp[i+k] - happyDp[i] > happyMax) {
                ret = i ;
                happyMax = happyDp[i+k] - happyDp[i];
                shyMin = shyDp[i+k] - shyDp[i];
            }

            // 得到啊该段长度
            if(happyDp[i+k] - happyDp[i] == happyMax
                    && shyDp[i+k] - shyDp[i] < shyMin) {
                ret = i;
                happyMax = happyDp[i+k] - happyDp[i];
                shyMin = shyDp[i+k] - shyDp[i];
            }
        }


//         输出
        System.out.println(ret+1);


    }


}


/**
 * 题目： 拓扑排序
 */

 class Main10 {
    public static PrintWriter out = new PrintWriter(new BufferedWriter(
            new OutputStreamWriter(System.out)));
    public static Read in = new Read();

    public static void main(String[] args) throws IOException {
        int n  = in.nextInt();
        int m  = in.nextInt();

        Map<Integer, List<Integer> > map = new HashMap<>();
        // hash 统计
        int[] hash = new int[n + 1];
        // 存储结果
        int[] ret = new int[n];

        // 输入并统计
        // 建图
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();


            if (!map.containsKey(x)) {
                // 入map
                map.put(x, new ArrayList<>());
            }


            // y 也进入
            map.get(x).add(y);

            // 统计
            hash[y]++;

        }

        // 入队列
        Queue<Integer> queue = new LinkedList<>();


        for (int i = 1; i <= n; i++) {


            // 入队列
            if (hash[i] == 0) {
                queue.add(i);
            }
        }

        int pos = 0;
        // 出队列
        while (!queue.isEmpty()) {
            int  x = queue.poll();

            ret[pos++] = x;

            for (int num : map.getOrDefault(x, new ArrayList<>())) {
                hash[num]--;
                // 一旦有 为 度为 0 就入队列
                if (hash[num] == 0) {
                    queue.add(num);
                }
            }
        }

        // 输出
        if (pos == n) {
            for (int i = 0; i < n - 1; i++) {
                out.print(ret[i] + " ");
            }

            out.println(ret[n - 1] );
        } else {
            out.println(-1);
        }




        out.close();
    }
}


class Read { // 自定义快速读入
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    String nextLine() throws IOException {
        return bf.readLine();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}




 class Main11 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        long x = in.nextLong();

        // 进行输入并打怪
        for(int i=0;i<n;i++) {
            long num = in.nextLong();
            if(x >= num) {
                x += num;
            } else {
                x += gcd(x,num);
            }
        }

        // 输出
        System.out.println(x);

    }

    public static long  gcd(long x, long y) {
        // 利用辗转相除法
        long tmp = x % y;


        while (tmp != 0) {
            x = y;
            y = tmp ;
            tmp = x % y;
        }


        return y;
    }
}


/**
 *  题目： 经过一役小红所向无敌
 *
 *  解法： 模拟
 */

 class Main12 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 光的
        long a = in.nextLong();
        long h = in.nextLong();

        // 对立的
        long b = in.nextLong();
        long k = in.nextLong();

        // 存储伤害
        long ret= 0;
        while(h  > 0 && k > 0) {
            // 累加伤害
            ret += (a+b);

            // 光受到对立的攻击
            h -= b;

            // 对立受到光的攻击
            k -= a;
        }

        // 假如 光 还活着
        if(h > 0) {
            ret += (a*10);
        }

        // 假如 对立 还活着
        if(k > 0) {
            ret += (b*10);
        }

        // 输出
        System.out.println(ret);
    }
}